package dynamicprogramming;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/4 20:45
 * https://leetcode-cn.com/problems/ones-and-zeroes/
 */
public class FindMaxForm {

    /**
     * 这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。
     * dp[i][j]表示含有i个0，j个1的背包最大子集长度
     * 地推公式：dp[i][j] = Math.max(dp[i][j], dp[i - I][j - J] + 1)
     * 初始化：dp[0][0] = 0
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s: strs) {
            int zeroNum = 0, oneNum = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {

    }
}
